package offer;

public class offer_0007 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0) return null;
        TreeNode root=new TreeNode(preorder[0]);
        tree(root,preorder,inorder,0, preorder.length-1,0,inorder.length-1);
        return root;
    }
    public TreeNode tree(TreeNode node,int[] pre,int[] in,int pleft,int pright,int ileft,int iright){
        if(pleft>pright||ileft>iright) return null;
        int index=pleft;
        for(int i=ileft;i<=iright;++i){
            if(in[i]==pre[pleft]){
                index=i;
                break;
            }
        }
        node.val=pre[pleft];
        node.left=new TreeNode(pre[pleft]);
        node.right=new TreeNode(pre[pleft]);
        node.left=tree(node.left,pre,in,pleft+1,index-ileft+pleft,ileft,index-1);
        node.right=tree(node.right,pre,in,index-ileft+1+pleft,pright,index+1,iright);
        return node;
    }
} class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }